package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 四数相加 {

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        fourSum(nums, 0);
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums == null){
            return new ArrayList<>();
        }
        int n = nums.length;
        quickSort(nums, 0, n - 1);
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0;i < n - 3;i++){
            for(int j = i + 1;j < n - 2;j++){
                int k = j + 1,l = n - 1;
                while(k < l){
                    int tmp = nums[i] + nums[j] + nums[k] + nums[l];
                    if(tmp == target){
                        result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        while(k < n - 1 && nums[k + 1] == nums[k]){
                            k++;
                        }
                        while(l > 2 && nums[l - 1] == nums[l]){
                            l--;
                        }
                        k++;
                        l--;
                    }else if(tmp > target){
                        l--;
                    }else{
                        k++;
                    }
                }
                while(j < n - 2 && nums[j + 1] == nums[j]){
                    j++;
                }
            }
            while(i < n - 3 && nums[i + 1] == nums[i]){
                i++;
            }

        }
        return result;
    }

    private static void quickSort(int[] nums, int begin, int end){
        if(begin >= end){
            return;
        }
        int i = begin, j = end, num = nums[begin];
        while(i < j){
            while(i < j && nums[j] > num){
                j--;
            }
            if(i < j){
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] < num){
                i++;
            }
            if(i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = num;
        quickSort(nums, begin, i - 1);
        quickSort(nums, i + 1, end);
    }
}
